<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  

  
  <title>数据结构与算法 学习笔记 | 个人博客</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="​                                                    数据结构与算法 学习笔记 概念   数据结构是计算机存储和组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 常见的数据结构   算法 概念 算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。 算法是一种解决">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构与算法 学习笔记">
<meta property="og:url" content="http://codercheng.cn/2021/04/08/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%20%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/index.html">
<meta property="og:site_name" content="个人博客">
<meta property="og:description" content="​                                                    数据结构与算法 学习笔记 概念   数据结构是计算机存储和组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 常见的数据结构   算法 概念 算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。 算法是一种解决">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/115715-115914.png">
<meta property="og:image" content="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/133929-579057.png">
<meta property="og:image" content="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/134434-109227.png">
<meta property="og:image" content="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/134528-921660.png">
<meta property="og:image" content="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/135241-268517.png">
<meta property="og:image" content="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/140121-568635.png">
<meta property="og:image" content="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/140135-774082.png">
<meta property="article:published_time" content="2021-04-08T05:41:46.308Z">
<meta property="article:modified_time" content="2021-04-08T06:25:43.854Z">
<meta property="article:author" content="CoderCheng">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/115715-115914.png">
  
    <link rel="alternate" href="/atom.xml" title="个人博客" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.lug.ustc.edu.cn/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

<meta name="generator" content="Hexo 4.2.1"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">个人博客</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="搜索"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://codercheng.cn"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-数据结构与算法 学习笔记" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2021/04/08/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%20%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/" class="article-date">
  <time datetime="2021-04-08T05:41:46.308Z" itemprop="datePublished">2021-04-08</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      数据结构与算法 学习笔记
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>​                                                    数据结构与算法 学习笔记</p>
<p>概念</p>
<p>  数据结构是计算机存储和组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。</p>
<p>常见的数据结构</p>
<p><img src="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/115715-115914.png" alt="image-20210408115710630"></p>
<p> <strong>算法</strong></p>
<p>概念</p>
<p>算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。</p>
<p><strong>算法是一种解决特定问题的思路。</strong></p>
<p>常见的算法</p>
<p><img src="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/133929-579057.png" alt="image-20210408133918634"></p>
<p>算法复杂度</p>
<p>我们采用时间复杂度和空间复杂度来计算</p>
<p><strong>时间复杂度</strong></p>
<p>T(n)=O(f(n)) </p>
<p><strong>空间复杂度</strong></p>
<p>空间复杂度全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系</p>
<p>比如将一个数组拷贝到另一个数组中，就是相当于空间扩大了一倍:T(n)=O(2n)，忽略系数即为O(n)</p>
<p><strong>线性表</strong></p>
<p>线性表（Linear List）就是数据排成像一条线一样的结构，数据只有前后两个方向</p>
<p><strong>数组</strong>（Array）是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结构</p>
<p>应用</p>
<p>数组是基础的数据结构，应用太广泛了，ArrayList、Redis、消息队列等等。</p>
<p><strong>链表（</strong>linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。</p>
<p>链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。（百度百科）</p>
<p>常见的链表包括：单链表、双向链表、循环链表</p>
<p><img src="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/134434-109227.png" alt="image-20210408134425525"></p>
<p>数组和链表是线性数据存储的物理存储结构：即顺序存储和链式存储。</p>
<p><strong>栈和队列都属于线性数据的逻辑存储结构</strong></p>
<p><img src="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/134528-921660.png" alt="image-20210408134511941"></p>
<p><strong>栈</strong>（stack）是一种线性数据结构，栈中的元素只能先入后出（First In Last Out，简称FILO）。</p>
<p>最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶 （top）。</p>
<p><strong>队列</strong></p>
<p>队列（queue）是一种线性数据结构，队列中的元素只能先入先出（First In First Out，简称 FIFO）。队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）。</p>
<p><strong>散列表</strong></p>
<p>散列表也叫作哈希表（hash table），这种数据结构提供了键（Key）和值（Value）的映射关系。只要</p>
<p>给出一个Key，就可以高效查找到它所匹配的Value，时间复杂度接近于O(1)。</p>
<p><strong>存储原理</strong></p>
<p><strong>哈希函数</strong></p>
<p>散列表在本质上也是一个<strong>数组</strong> 散列表的Key则是以字符串类型为主的通过hash函数把Key和数组下标进行转换</p>
<p>作用是把任意长度的输入通过散列算法转换成固定类型、固定长度的散列值。</p>
<p>递归，去的过程叫”递”，回来的过程叫”归</p>
<p><strong>递归三要素</strong></p>
<ul>
<li><p>递归结束条件</p>
</li>
<li><p>函数的功能 </p>
<p>这个函数要干什么，打印，计算</p>
</li>
<li><p>函数的等价关系式</p>
<p>递归公式，一般是每次执行之间，或者与个数之间的逻辑关系</p>
</li>
</ul>
<p><strong>二分查找</strong></p>
<p>二分查找（Binary Search）算法，也叫折半查找算法</p>
<p>有很多数据的逻辑关系并不是线性关系，在实际场景中，常常存在着一对多，甚至是多对多的情况。家谱</p>
<p><img src="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/135241-268517.png" alt="image-20210408135241370"></p>
<p><strong>二叉树</strong></p>
<p>二叉树（binary tree）是树的一种特殊形式。二叉，顾名思义，这种树的每个节点最多有2个孩子节点。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点</p>
<p><strong>二叉查找树</strong></p>
<p>二叉查找树(binary search tree)，二叉查找树在二叉树的基础上增加了以下几个条件</p>
<p>如果左子树不为空，则左子树上所有节点的值均小于根节点的值</p>
<p>如果右子树不为空，则右子树上所有节点的值均大于根节点的值</p>
<p>左、右子树也都是二叉查找树</p>
<p> <strong>广度优先遍历（BFS，Breadth First Search）</strong></p>
<p>也叫层序遍历，顾名思义，就是二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点。</p>
<p><strong>深度优先搜索（DFS   Depth First Search）</strong></p>
<p>深度优先搜索，从起点出发，从规定的方向中选择其中一个不断地向前走，直到无法继续为止，然后尝</p>
<p>试另外一种方向，直到最后走到终点。就像走迷宫一样，尽量往深处走。</p>
<p>二叉查找树的插入和查找时间复杂度为:O(logn)</p>
<p>极端情况下二叉查找树退化成链表，时间复杂度为O(n)，所以需要平衡二叉查找树。</p>
<p><strong>红黑树</strong></p>
<p>红黑树就是一种自平衡的二叉查找树</p>
<p>除了二叉查找树(BST)的特征外，还有以下特征：</p>
<p>每个节点要么是黑色，要么是红色</p>
<p>根节点是黑色</p>
<p>每个叶子节点都是黑色的空结点（NIL结点）（为了简单期间，一般会省略该节点）</p>
<p>如果一个节点是红色的，则它的子节点必须是黑色的（父子不能同为红）</p>
<p>从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点（平衡的关键）</p>
<p>新插入节点默认为红色，插入后需要校验红黑树是否符合规则，不符合则需要进行平衡</p>
<p><strong>多路查找树</strong></p>
<p>*<em>多路查找树(muitl-way search tree)，其每一个节点的孩子数可以多于两个，且每一个节点处可以存储多个元素 *</em> 。</p>
<p>B树（BalanceTree）是对二叉查找树的改进。它的设计思想是，将相关数据尽量集中在一起，以便一</p>
<p>次读取多个数据，减少硬盘操作次数</p>
<p><img src="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/140121-568635.png" alt="image-20210408140120320"></p>
<p>B+树是B-树的变体，也是一种多路搜索树，其定义基本与B树相同，它的自身特征是：</p>
<p>非叶子结点的子树指针与关键字个数相同</p>
<p>非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树</p>
<p>所有关键字都在叶子结点出现</p>
<p>为所有叶子结点增加一个链指针</p>
<p><img src="https://gitee.com/adc123321/blog_img/raw/master/image/202104/08/140135-774082.png" alt="image-20210408140134258"></p>
<p><strong>典型应用</strong></p>
<p>MySQL索引B+Tree</p>
<p>B树是为了磁盘或其它存储设备而设计的一种多叉（下面你会看到，相对于二叉，B树每个内结点有多个</p>
<p>分支，即多叉）平衡查找树。 多叉平衡</p>
<p>B树的高度一般都是在2-4这个高度，树的高度直接影响IO读写的次数。</p>
<p>如果是三层树结构—支撑的数据可以达到20G，如果是四层树结构—支撑的数据可以达到几十T </p>
<p>B和B+的区别</p>
<p>B树和B+树的最大区别在于<strong>非叶子节点是否存储数据</strong>的问题。</p>
<p><strong>二叉堆</strong></p>
<p>二叉堆本质上是一种完全二叉树，它分为两个类型</p>
<p>大顶堆(最大堆)</p>
<p>最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值</p>
<p>小顶堆(最小堆)</p>
<p>最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值</p>
<p><strong>算法思维</strong></p>
<p><strong>贪婪算法</strong>（Greedy）的定义：是一种在每一步选中都采取在当前状态下最好或最优的选择，从而希望</p>
<p>导致结果是全局最好或最优的算法</p>
<p>贪婪算法：当下做局部最优判断，不能回退</p>
<p><strong>经典问题</strong></p>
<p><strong>部分背包问题</strong></p>
<p><strong>适用场景</strong></p>
<p>针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值</p>
<p>最大。</p>
<p><strong>分治算法</strong></p>
<p>分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n</p>
<p>个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原</p>
<p>问题的解。</p>
<p>关于分治和递归的区别</p>
<p>分治算法是一种处理问题的思想，递归是一种编程技巧</p>
<p><strong>经典问题</strong></p>
<p><strong>字符串转大写</strong></p>
<p><strong>回溯算法</strong></p>
<p>回溯算法实际上一个类似枚举的深度优先搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发</p>
<p>现已不满足求解条件时，就“回溯”返回（也就是递归返回），尝试别的路径</p>
<p><strong>经典问题                 N皇后问题</strong></p>
<p><strong>动态规划</strong></p>
<p>动态规划(Dynamic Programming)，是一种分阶段求解的方法。</p>
<p>动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）</p>
<p>的方式去解决。</p>
<p>动态规划中有三个重要概念：</p>
<ul>
<li><p>最优子结构</p>
</li>
<li><p>边界</p>
</li>
<li><p>状态转移公式（递推方程）dp方程</p>
</li>
</ul>
<p><strong>经典问题             01 背包问题</strong></p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://codercheng.cn/2021/04/08/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%20%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/" data-id="cko3snvxm001ui8uo88ic4z1k" class="article-share-link">Share</a>
      
      
    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2021/04/09/%E5%88%A4%E6%96%AD%E6%95%B0%E7%BB%84%E6%98%AF%E5%90%A6%E6%9C%89%E9%87%8D%E5%A4%8D%E6%95%B0%E5%AD%97%20%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6O(n)/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          判断数组是否有重复数字 时间复杂度O(n)
        
      </div>
    </a>
  
  
    <a href="/2021/03/31/k8s/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">k8s</div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">分类</h3>
    <div class="widget">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/Java/">Java</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/MySql/">MySql</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/Netty/">Netty</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/SpringBoot/">SpringBoot</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/SpringCloud/">SpringCloud</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/SpringMVC/">SpringMVC</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/Tomcat/">Tomcat</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/Zookeeper/">Zookeeper</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E4%BD%9C%E4%B8%9A/">作业</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E5%88%86%E5%B8%83%E5%BC%8F%E8%B0%83%E5%BA%A6/">分布式调度</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E6%A1%86%E6%9E%B6/">框架</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E7%9F%A5%E8%AF%86/">知识</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/">设计模式</a></li></ul>
    </div>
  </div>


  
    

  
    
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">归档</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2024/08/">八月 2024</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/09/">九月 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/08/">八月 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/04/">四月 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/02/">二月 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/11/">十一月 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/06/">六月 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/05/">五月 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/04/">四月 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/03/">三月 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/02/">二月 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/01/">一月 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/12/">十二月 2020</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/11/">十一月 2020</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/10/">十月 2020</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/09/">九月 2020</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/08/">八月 2020</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">最新文章</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2024/08/28/CentOS%E5%86%85%E5%AD%98cpu%E6%8E%92%E6%9F%A5/">CentOS内存cpu排查</a>
          </li>
        
          <li>
            <a href="/2022/09/22/Linux%20%E6%9F%A5%E7%9C%8B%E6%97%A5%E5%BF%97%E5%91%BD%E4%BB%A4/">Linux 查看日志命令</a>
          </li>
        
          <li>
            <a href="/2022/08/30/dubbo%20%E5%B8%B8%E8%A7%81%E9%97%AE%E9%A2%98/">dubbo 常见问题</a>
          </li>
        
          <li>
            <a href="/2022/04/26/1%20%E6%BA%90%E7%A0%81%E7%AC%94%E8%AE%B0/">1 源码笔记</a>
          </li>
        
          <li>
            <a href="/2022/02/24/jvisualVM%20%E4%BD%BF%E7%94%A8%E7%AC%94%E8%AE%B0/">jvisualVM 使用笔记</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2024 CoderCheng<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//code.jquery.com/jquery-2.0.3.min.js"></script>


  
<link rel="stylesheet" href="/fancybox/jquery.fancybox.css">

  
<script src="/fancybox/jquery.fancybox.pack.js"></script>




<script src="/js/script.js"></script>




  </div>
</body>
</html>